%%%-------------------------------------------------------------------
%%% File    : p49.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The arithmetic sequence, 1487, 4817, 8147, in which each of the 
%%% terms increases by 3330, is unusual in two ways: (i) each of the 
%%% three terms are prime, and, (ii) each of the 4-digit numbers are 
%%% permutations of one another.
%%%
%%% There are no arithmetic sequences made up of three 1-, 2-, or 
%%% 3-digit primes, exhibiting this property, but there is one other 
%%% 4-digit increasing sequence.
%%%
%%% What 12-digit number do you form by concatenating the three terms in this sequence?
%%%
%%%
%%% Created :  4 Jan 2009
%%%-------------------------------------------------------------------
-module(p49).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: solution(Min, Max) -> list() 
%% 
%% Description: Return a list of lists of the numbers between Min and Max which are prime, permutations of 
%% each other and are an arithmetic sequence.
%%--------------------------------------------------------------------
%Create a table with
solution(Min, Max) ->
    Tbl = for(3, Min, Max, [2], ets:new(lookup, [])), 
    MoreThan3 = ets:foldl(fun({_, Count, _}, Acc) when Count < 3-> Acc;
                 ({_, _, Numbers}, Acc) -> [Numbers|Acc]
              end,
             [],
             Tbl),
    Filtered = [[{A, B, C} || A <- List, B <- List, C <- List, A > B, B > C, A - B =:= B - C]|| List <- MoreThan3],
    lists:filter(fun(Item) -> length(Item) > 0 end, Filtered).

%%====================================================================
%% Internal functions
%%====================================================================
%Iterate through all primes and create a table mapping their digits (sorted) to a list of all prime permutations of
% these digits and their count.
for(I, _, Max, _, Tbl) when I > Max-> Tbl;
for(I, Min, Max, Primes, Tbl) ->
    NewPrimes = case is_prime(I, math:sqrt(I),Primes) of
                    true when I > Min ->
                        Digits = lists:sort(digits(I, [])),
                        Old = ets:lookup(Tbl, Digits),
                        case Old of
                            [] ->
                                ets:insert(Tbl, {Digits, 1, [I]});
                            [{_, N, Prev}] -> ets:insert(Tbl, {Digits, N + 1, [I|Prev]})
                        end,
                        Primes++[I];
                    true ->
                        Primes++[I];
                    _ -> Primes
                end,
    for(I + 2,Min, Max, NewPrimes, Tbl).

%Return a list of the digits of a Number
digits(0, Acc) -> Acc;
digits(N, Acc) -> digits(N div 10, [N rem 10|Acc]).

%Check if a number is prime using the list of all previous primes.
is_prime(_, _, []) -> true;
is_prime(_, Sqrt, [H|_]) when H > Sqrt -> true; 
is_prime(N, _, [H|_]) when N rem H =:= 0 -> false; 
is_prime(N, Sqrt, [_|T]) -> is_prime(N, Sqrt, T).
